但显然有单调栈关系。第 $i$ 个区间覆盖的实际是 $[L_i, R_i] = [\max(X_i, X_{pre} + U), \min(X_i + U, X_{nxt})]$ 其中 $pre$ 和 $nxt$ 是最近的两个 $B < B_i$ 的位置。$ans = \sum_i B_i * (R_i - L_i)$

容易算出从每个 $S$ 到 $n + 1$ 的答案，而 $S$ 到 $T$ 的答案减去覆盖了 $T$ 的那个区间多覆盖的部分即可。

倒做，离散化，BIT 维护 $ans$

hint：$L < R$ 当且仅当 $X_{nxt} - X_{pre} > u$。

$Code$

门票安排

看题解.gif

来复读啦

考虑两个被反转的区间如果无交那一定不优。因此所有被反转的区间都有公共部分。

设公共部分为 $[l, r]$，$a_i$ 为都不反转时的覆盖次数，$b_i$ 为最终的覆盖次数，$t$ 为 $[l, r]$ 中 $b$ 最大的位置

有三个定理：

$b_t \geq \max(b_i) - 1$

反证：如果 $b_t \leq \max(b_i) - 2$ 那么反转一个 $[l, r]$ 的区间答案不会变劣。
$a_t = \max(a_i)$

反证：若存在 $a_p > a_t$ 且 $p \notin [l, r]$，根据定义至少存在一个区间不包含 $p$，即 $a_p - b_p \leq a_t - b_t - 1$，$b_p - b_t \geq a_p - a_t + 1$, $b_p - b_t \geq 2$，与定理 $1$ 矛盾。
$\forall a_k = \max(a_i), k \in [l, r]$

证明类似定理 $2$。

二分答案 $ans$, $ans = b_t = a_t - 反转个数 cnt$ 或 $ans = b_t + 1 = a_t - cnt + 1$

关于判定，$ans$ 确定了 $cnt$ 也就确定了，chk 能否在 $cnt$ 次内完成。从左到右扫，当前位置 $i$，每次把 $l \leq i$, $r \geq t$ 的区间加入以 $r$ 为第一关键字的大根堆。设还应反转区间个数为 $x$，若 $a_i - (cnt - x) + x > ans$ 则弹出并反转堆顶区间。那么当前已反转个数能算出，不足就补。

至于正确性，性感理解一下，优先反转 $r$ 大的对后续最有利且负面影响最小。

$Code$

长途巴士

~~话说 JOI 的题，堆啊贪心啊取模啊都运用得很溜诶~~

把人和服务站都拍在 $[0, T)$ 的数轴上。接下来的顺序都是按数轴来。

考虑怎么踢掉不想要的人，如果存在 $S_j \mod T \in (D_i, D_{i + 1})$ 那就可以成功踢走 $[x, i] (1 \leq x \leq i)$ 的人。踢人肯定是一段一段踢，并且每段在对应最早的 $j$ 出现时踢。

就可以设计 dp：$f_i$ 表示考虑数轴上前 $i$ 个乘客的最小花费，根据 $i$ 选不选有两种转移：

$f_i = f_{i - 1} + (\lfloor \frac{X - D_i}{T} \rfloor + 1) * W$
$f_i = \min\limits_{0 \leq j < i}( f_j + calc(j + 1, i) )$，其中 $calc(l, r) = (r - l + 1) W ( \min\limits_{S_k \mod T \in (D_r, D_{r + 1})}( \lfloor \frac{S_k}{T} \rfloor ) + (preC_{r} - preC_{l - 1}) )$

斜优即可。

$Code$

幽深府邸

为什么「幽深府邸」原文是「细长的屋敷」啊【/笑cry】本题是某 HNOI2018 的非严格加强版。原题写了线段树一只 $log$，但是暴力更新 + 二分也是一只 $log$ 的，而且好写到不知道哪里去了

复杂度证明的话，每个位置只会被最小区间统计一次。

$Code$

自然公园

神仙交互题，做不来做不来

$Ask(x, y, P)$ 表示能否只用 $P$ 中的点使 $x$ 和 $y$ 连通。

可能的使用姿势：询问一堆点的补集以确定这些点中是否有必经点。

链怎么做？考虑分治做 $[l, r]$，询问 $O(lstlen)$ 次确定夹在 $[l, r]$ 中的点然后取一个中点 $mid$，递归做，$O(nlogn)$。
树怎么做？考虑以 $x$ 为根的连通块，每次找一个块外点 $z$，找到块中离 $z$ 最近的点 $y$，接下来就是做 $y \rightarrow z$ 这条链。实现用点分治。
图怎么做？考虑以 $x$ 为根的连通块，每次拓展块外相邻点 $x$，具体来说选一个块外点然后二分找到离块最近的。

怎么给 $x$ 找块内与它直接相连的点？搞出块的 dfs/bfs 序，找到当前与 $x$ 连通的序最小的点，连边并删除。大概是 $n^2$ 的，询问 $nlogn$。

细节一大堆，烦死了 /fn

$Code$

JOI 2018 Final

这套好水啊……

团子制作

对于两个 $G$ 如果他们不在同一东北-西南方向对角线的相邻位置是绝不会互相影响的。每条对角线单独 dp。

$Code$

月票购买

题意：给出一张无向图和 $s$，$t$，$u$，$v$，你可以钦定一条 $s \rightarrow t$ 的最短路并把路径上所有边的边权改为 $0$，然后最小化 $u \rightarrow v$ 的最短路。

显然是在所有 $s$ 到 $t$ 最短路上找两个点 $(i, j)$，满足 $u \rightarrow i \rightarrow j \rightarrow v$ 最小。

好办，枚举 $j$，求前/后缀最小即可。是否在最短路上——这不是随便判嘛？$dis[x] + w = dis[y]$！

$Code$

考试

一眼做法：设 $z = x + y$，$(x, y, z)$ 做三维偏序。没意思！

考虑几何意义：求一个两条直线和坐标轴平行、一个角被切掉的图形内包含的点数。

考虑容斥！$c = \max(c, a + b)$（这样就把 $c$ 这条限制代表的斜线移到 $(a, b)$ 右上方去啦，使得 $ans$ 中的后两项无交）

$ans = \sum [总分 < c] - \sum [总分 \geq c 但 a 偏小] - \sum [总分 \geq c 但 b 偏小]$

$Code$

馕

膜题解。优美的贪心！

预处理每个人的 $n$ 等分位置。第 $i$ 次选还没安排的人里第 $i$ 个 $n$ 等分点最小的。可以归纳证明每个时刻的右端点一定是所有方案里最小的。

$Code$

两道料理

$f[i, j] = \max( f[i - 1, j] + p_i [ sa_i + sb_j \leq s_i ] (\mathbb{I}), f[i, j - 1] + q_j [ sa_i + sb_j \leq t_j ] (\mathbb{II}) )$

对每个 $i$ 处理出 $mxu_i$ 满足 $\mathbb{I}$ 中方括号成立，对每个 $j$ 处理出 $mxr_j$ 满足 $\mathbb{II}$ 中方括号成立

那么一条从 $(0, 0)$ 走到 $(n, m)$ 的路径，如果 $(i, mxu_i)$ 在路径上或路径上方就产生贡献，如果 $(mxr_j, j)$ 在路径上或路径下方就产生贡献。

$(i, j)$ 不在路径上或路径上方，即 $(i, j)$ 在路径下方，当且仅当 $(i - 1, j + 1)$ 在路径上或路径下方

$sum[i, j]$ 表示 $(i, j)$ 正下方的贡献和

$f[i, j] = \max(f[i, j - 1], f[i - 1, j] + sum[i, j])$

线段树维护前缀最大值差分，正数直接单点加，负数往后消，消不完就算了（虽然但是我不懂复杂度怎么算……

$Code$

两个天线

设坐标为 $d$

离线询问，按右端点排序。怎么统计所有 $(i, j)$ 的贡献？我们的策略是枚举 $j$，把贡献放在 $i$ 上。

$i$ 在 $i + A_i$ 时变得可用，在 $i + B_i + 1$ 时变得不可用

每次新加入一个 $j$，将 $[j - B_j, j - A_j]$ 里可用的 $i$ 上的权值对 $H_i - H_j$ 取 $\max$

实用的 trick 是让 $H_i$ 在 $i$ 可用时为其本来值，在 $i$ 不可用时为 $-\infty$

查询就查整个区间的 $i$ 的权值 $\max$

绝对值嘛，取相反数，做两遍就好了

$Code$ ~~调写的时候 sb 错误一大堆，你可能需要去上个厕所~~

指定城市

维护当前的「双向边」连通块，「双向边」连通块不会再对答案有贡献

$E = 1$ 可以换根 dp 做，$E = 2$ 可以把所有的 $(x, y)$ 放到 $LCA(x, y)$ 上去统计。

设第 $i$ 次选的点集为 $S_i$，有个结论是 $i \geq 2$ 时 $S_i \subseteq S_{i + 1}$，所以之后的贪心选即可。

$Code$

开关游戏

性质一看一大堆。

操作序列中如果前一个是 TOG，后一个是 ON/OFF 且他们相交，可以交换顺序。

——那干脆把 ON/OFF 都排到操作序列的前段！

ON/OFF 彼此不相交。TOG 彼此显然不交。画一下图发现非常清真。

$dp_{i, 0/1/2}$ 表示第 $i$ 盏灯未被赋值/被赋值$’0’$/$’1’$ 时需要的操作次数的两倍（为了方便统计 TOG）。

hint：串开头结尾各加一个 $’0’$ 可以少一些边界 case。

$Code$

蛋糕拼接

简单题？按 $C$ 排序，显然 $C$ 只和两端位置有关，$ans = \sum V_i - 2 * ( C_M - C_1 )$
对于 $l_1 < l_2$

感性理解新加入一个 $r$ 对 $l_1$ 产生的收益小于等于 $l_2$（$C$ 之差！），即，若对于 $r_0$，$l_2$ 优于 $l_1$，那么对于 $r \geq r_0$，$l_2$ 都优于 $l_1$。其决策单调性得证。

分治求出每个 $l$ 对应的 $r$。

区间查前 $K$ 大，主席树板子！

$Code$

穿越时空 Bitaro

DS 题！放官图：

picture_in_Official_solution

路线是条斜率为 $1$ 的折线。我们要最小化竖线个数。

严格上升很讨厌，将第 $i$ 列整体向下移 $i$ 单位，走路时间就变成 $0$ 了。

关于一段有始有终的路径，维护两个分段函数:

$f(x)$ 表示 $x$ 时间走进去，什么时候走出来
$g(x)$ 表示 $x$ 时间走进去，使用多少次特技走出来

$f(x)$ 是两段平，中间是 $y = x + k$；$g(x)$ 是前面一段平，后面是 $y = x + k$

考虑合并，发现函数形状不会改变。线段树维护。

结构体的定义是：$(l, r, x, y)$ 表示 $f(x)$ 两个端点是 $(l, x - (r - l))$ 和 $(r, x)$，$g(x)$ 端点是 $(r, y)$

$Code$

合并

感觉像分治。

我们可以通过 $2n$ 次询问将 $2n$ 个宝石分在两个集合 $A$、$B$ 中，满足相同集合内宝石种类互不相同。

考虑将 $B$ 与 $A$ 匹配。

把 $A$ pia 成两半，通过长度次询问能确定 $B$ 中元素应当在哪半。

递归下去做即可。

假设每次取前 $pn$ 个（$n$ 是当前 $A$ 长度）

$F(n) = F(pn) + F((1 - p)n) + pn + n$

$p$ 取 $\frac{3 - \sqrt{5}}{2}$ 时最优，大概询问 $980000$ 次。

$Code$

回转寿司

给了 $9s$，操作又不是很好维护，考虑分块（JOISC 竟然出分块题！

每个块搞个堆，散块暴力，整块删除最大值，加入新最小值即可。

考虑整块标记怎么下推。注意到标记之间的顺序没有影响，从左到右推一遍即可。

标记下推还是挺有意思的。

$Code$

糖

第一反应决策单调性？emmmm；第二反应增广…… emm xml 你拟阵学傻了吧！第三反应反悔贪心。呼呼总算正常了。

$Code$

图书馆

做你丫的交互，劳资快乐 SCT 去了 ~~（SAM + LCT）~~

女装大佬

题意杀——同一分钟里，领取男女装的事件同时进行。

剩下的 M 个数需要 $\leq$ F，即，将 F 视作 $1$，M 视作 $-1$，要满足最小后缀 $\geq -1$，且要使最大的不满意值最小。

从后往前扫，小于 $-1$ 就从把前面最近的 F 拿过来，发现这样代价最小并且恰好是 $- sufmin - 1$。

$Code$

道路建设

题意：求某个点到根的链的逆序对，然后对链做区间赋值

每条链可以被划分为若干权值相同的段。考虑每个颜色相同且深度递增的段维护一个 splay——就是 LCT 啦！每棵 LCT 维护子树大小也就是该颜色的个数，access 时用 BIT 记一下每种颜色的个数。复杂度分析参考 LCT。

$Code$

帐篷

题意：每个点，其四个方向最多只有一个点。我们称「自由点」为四面都没有点的点。该方案的权值为 $4^{自由点数}$

只要知道了空余的行和列数就可以了？好像很难记录状态。

考虑扣掉一个自由点，空出来的一行一列删掉也不会有影响；扣掉一对点，空出来的一行两列或两行一列删掉不会有影响。

于是直接 $f[n, m]$ 表示 $n * m$ 的答案。每次新加一列，有：

$f[n, m] = f[n, m - 1] + f[n - 1, m - 1] n 4 + \binom{n}{2} f[n - 2, m - 1] + n (m - 1) * f[n - 1, m - 2]$

$Code$

修行

再一次被计数题杀。。。

等价于有多少排列 $a_i > a_{i + 1}$ 的 $i$ 个数为 $k - 1$

转化为求期望。（？？怎么想到的）

等价于 $n$ 个 $[0, 1)$ 随机变量 $a_i > a_{i + 1}$ 的个数为 $k - 1$

等价于 $n$ 个 $[0, 1)$ 随机变量 $b_i$ 前缀和的小数部分，前一个大于后一个的个数为 $k - 1$

等价于求 $k - 1 \leq \sum b_i < k$

容斥 $[0, 1)$ 的限制，枚举 $\geq 1$ 的个数 $i$，那么问题转化为 $n$ 个非负变量之和 $< k - i$ 的方案数，$= \frac{(k - i)^n}{n!}$，大概意思是在长度为 $k - i$ 的段里选 $n$ 个节点划分 $n$ 段的方案数。

最差记者 3

~~听说是提高组题，自己想想。~~ 最后还是看题解了 /dk

每个人的周期是可以计算的。如果当前人的周期小于上个人的周期，那他的新周期等于上个人的周期。
否则他的新周期 $f_i = \lceil \frac{f_{i - 1}}{d_i} \rceil$

然后就是非常神必的一步：该函数每次减少一半左右……

所以把这个分段函数存下来就行。$O(QlogD)$

实现是我最讨厌的细节！！！啊！

野猪

设某条有向路径 $path$ 的最后一条边为 $lst_{path}$

上一次 $X$ -> $Y$，那么 $Y$ -> $X$ 只会走：

除掉 $lst_{path(x, y)}$ 的最短路 $minpath$
除掉 $lst_{path(x, y)}$ 和 $lst_{minpath}$ 的最短路

相当于对于每一对点 $(X, Y)$，求出：

最短路
和最短路首边不同的最短路
和最短路首边不同且和 2 末边不同的最短路
和最短路末边不同的最短路
和最短路末边不同且和 4 首边不同的最短路

（23 和 45 就是反一下）

你发现就是把边当作点去求最短路嘛！

菊花图直接卡飞，单次 $O(m^2)$

$f[i, j]$ 表示走到 $i$ 节点，最后经过的边是 $j$ 的最小代价，发现这样总状态是 $O(n)$，转移按点来，也是 $O(n)$ 的。直接相连的点对要特殊处理。

考虑修改。并不是只会改与修改点相邻的两条路径啊！可能会波及到挺远，所以你需要——SGT！对每个区间维护以上五种类型的路径，复杂度 $O(m^2logm + 5^3 T log L)$

$Code$

俄罗斯套娃

显然这是个 DAG 上的偏序关系。就是求 DAG 的最小链精确覆盖。

画在 $R$ 为 $x$ 坐标、$H$ 为 $y$ 坐标的图上比较直观，询问变成一个四分之一平面

根据 Dilworth 定理，最小链精确覆盖 = 最长反链，即这题中的最长不升子序列（即 $R$ 增 $H$ 不增）

考虑离线询问和点，按 $R$ 从大到小排序，BIT 维护当前高度区间为 $[1, x]$ 的最长不升子序列

$Code$